Search for: All records

In the light bulb problem, one is given uniformly random vectors x1,…,xn,y1,…,yn∈{−1,1}d. They are all chosen independently except a planted pair (xi∗,yj∗) is chosen with correlation ρ>0. The goal is to find the planted pair. This problem was introduced over 30 years ago by L.~Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in Ω(n2) time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as ρ→0. In 2012, G.~Valiant gave a breakthrough algorithm using fast matrix multiplication that runs in time O(n(5−ω)/(4−ω))0 is. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to O(n2ω/3)0. We also introduce a new tensor T2112, which has the same size of 2×2 matrix multiplication tensor, but runs faster than the Strassen's algorithm for light bulb problem. 

We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.